package leetcode.code0473;

import java.util.HashMap;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//
public class Solution3 implements IDebug {

	public boolean makesquare(int[] matchsticks) {
		int total = 0;
		Map<Integer, Integer> matchs = new HashMap<>();
		int p = 0;
		for (int num : matchsticks) {
			total += num;
			matchs.put(1 << p++, num);
		}
		if (total % 4 != 0) {
			return false;
		}
		int aim = total / 4;
		int len = matchsticks.length;
		int limit = (1 << len) - 1;
		Map<Integer, Boolean> dp = new HashMap<>();
		return this.find(matchs, 4, aim, limit, 0, dp);
	}

	private boolean find(Map<Integer, Integer> matchs, int num, int aim, int limit, int sum, Map<Integer, Boolean> dp) {
		if (num == 0) {
			return limit == 0;
		}
		if (dp.containsKey(limit)) {
			return dp.get(limit);
		}
		int chose = limit;
		while (chose != 0) {
			int find = chose & -chose;
			int tyr = matchs.get(find);
			if (sum + tyr == aim) {
				boolean rs = this.find(matchs, num - 1, aim, limit - find, 0, dp);
				if (rs) {
					return true;
				}
			} else if (sum + tyr < aim) {
				boolean rs = this.find(matchs, num, aim, limit - find, sum + tyr, dp);
				if (rs) {
					return true;
				}
			}
			chose -= find;
		}
		dp.put(limit, false);
		return false;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(true, this.makesquare(HelpDebug.str2array3("[5,5,5,5,4,4,4,4,3,3,3,3]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(false, this.makesquare(HelpDebug.str2array3("[5,5,5,5,16,4,4,4,4,4,3,3,3,3,4]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
